package com.julius.design.suanfa.dynamic;

import java.util.HashMap;

/**
 * @author julius
 * @date 2021-11-01 上午 11:28
 * <p>
 *      最长不含重复字符的子字符串
 *      请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。、
 *
 *      https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
 * </p>
 */
public class LengthOfLongestSubstring {


    /**
     * 动态规划（最值问题）：
     *      状态定义：
     *          dp[i] 代表以第i的字符结尾的不重复子串的最大长度
     *          dp[i-1] 代表以第i-1位置的字符结尾的不重复字串的最大长度
     *      状态转移方程：
     *          遇到重复的就需要将第一个重复的指针后移，并将不重复长度重新计算（利用字符下标）
     *          dp[i] = d[i-1]+1，i-start
     *
     *      初始值：
     *          当时字符串长度为1时，dp[1] = 1
     *
     *      返回值：
     *          max(dp[0:i])
     *
     *  0 1 2 3 4 5 6 7 8 9
     *  a a b c e a f c b b
     *
     *  3
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        //首先找不重复的所有字串，然后对比所有字串长度（暴力解法）
        //如何找到不重复字串呢，
        if(s == null || s.length() == 0){
            return 0;
        }
        //优化后的dp数组
        int max = 1;
        HashMap<Character,Integer> cache = new HashMap<>();
        cache.put(s.charAt(0),0);
        int start = 0;int temp = 1;
        for (int i = 1;i < s.length();i++){
            Integer oldIndex = cache.get(s.charAt(i));
            if(oldIndex != null && start <= oldIndex){
                //字符重复,重新计算最大不重复长度
                temp = i - oldIndex;
                start = oldIndex+1;
            }else{
                temp++;
            }
            //加入缓存
            cache.put(s.charAt(i),i);
            max = Math.max(max,temp);
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println("最大不重复子串长度："+lengthOfLongestSubstring("abba"));
    }
}
